//
//  MinimumCostAnalyzer.cpp
//  RoutingEvaluator
//
//  Created by Christopher Kemsley on 4/15/12.
//  Copyright (c) 2012 iAppolopolis. All rights reserved.
//

#import <Foundation/Foundation.h>
#include <set>
#include <map>
#include <sstream>
#include <string>
#import "Analyzer.hpp"
#import "Node.hpp"
#import "Link.hpp"
#import "OCNodeInfo.h"
#import "OCLinkInfo.h"

NamespaceBegin



struct MinimumSpanningAnalyzer : Analyzer
{
	MinimumSpanningAnalyzer () : Analyzer ( "Minimum Spanning Tree" ) { }
	
	
	static void		enumerateLinkVectorUnion	( LinkVector const & v1 , LinkVector const & v2 , void(^block)(Link*) )
		{
		bool (^isInList2)(Link*) = ^bool(Link*l) {
			LinkVector::const_iterator	h	=	v2.begin() ;
			LinkVector::const_iterator	e	=	v2.end() ;
			while ( h < e )
				if ( (*(h++)) == l ) return true ;
			return false ;
		} ;
		
		LinkVector::const_iterator	h	=	v1.begin() ;
		LinkVector::const_iterator	e	=	v1.end() ;
		while ( h < e )
			{
			Link * l = *(h++) ;
			if ( isInList2(l) )
				block ( l ) ;
			}
		}
	
	
	virtual void	analyze		( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , PropertySet const & info , Output & output )
		{
		Float64		maxRange	=	20 ; // 20 is the default
		info . getValue ( "maxRange" , maxRange ) ;
		
		UInteger	startNode	=	1 ;
		info . getValue ( "referenceNode" , startNode ) ;
		
		
		
		NodeSet	*	nodes		=	NodeSet :: createSetWithNodes(nodesInfo) ;
		LinkVector	links ;
		
		Node	*	rootNode	=	nodes -> nodeWithIdentifier ( startNode ) ;
		
		
		
		generateTopology ( nodesInfo , linksInfo , maxRange , startNode , nodes , links ) ;
		
		
		
		
		
		// Calculate the sum
		
		__block Float64	sum	=	0 ;
		__block NSUInteger count = 0 ;
		calculateTotalCost ( rootNode , links , ^(Float64 c){count++;sum+=c;} , 0 ) ;
		
		output.tableOut() << "Property	Value" ;
		
		output.tableOut() << "\nTotal Energy	" << sum ;
		output.tableOut() << "\nTransmission Count	" << count ;
		
		
		
		
		
		output.drawNetworkTopology ( nodes , links ) ;
		}
	
	
	static void		calculateTotalCost	( Node * rootNode , LinkVector const & activeLinks , void(^addCost)(Float64) , Link * receivingLink )
		{
		__block Float64 max = 0 ;
		enumerateLinkVectorUnion ( activeLinks , rootNode->links() , ^(Link* l){
			Float64 c = l->identity->cost() ;
			if ( l != receivingLink )
				{
				if ( c > max )
					max = c ;
				
				Node * otherSide = l -> nodeOppositeFrom ( rootNode ) ;
				
				if ( otherSide==0 )
					[NSException raise:NSInternalInconsistencyException format:@"Link didn't return an opposite endpoing when calculating cost"] ;
				
				calculateTotalCost ( otherSide , activeLinks , addCost , l ) ;
				}
		}) ;
		if ( max != 0 ) addCost ( max ) ;
		}
	
	static void		generateTopology ( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , Float64 maxRange , UInteger startNode , NodeSet * nodes , LinkVector & links )
		{
		if ( nodesInfo->nodes().size() < 2 )
			[NSException raise:NSInternalInconsistencyException format:@"Algorithm doesn't make sense with <2 other nodes."] ;
		
		
		
		
		NSMutableSet	*	unreachedNodes	=	[NSMutableSet setWithCapacity:nodesInfo->nodes().size()] ;
		NSMutableSet	*	networkedNodes	=	[NSMutableSet setWithCapacity:nodesInfo->nodes().size()] ;
		
		NSSet			*	allLinks		=	[OCLinkInfo linkInfoSet:linksInfo] ;
		NSMutableSet	*	activeLinks		=	[NSMutableSet setWithCapacity:nodesInfo->nodes().size()] ;
		
		
		
		
		
		/* Verify link count */
		
		NSUInteger	sum	=	0 ;
		NSUInteger	m=nodesInfo->nodes().size() ;
		while ( --m ) sum += m ;
		
		if ( allLinks.count != sum )
			[NSException raise:NSInternalInconsistencyException format:@"Incorect link count. Expected %lu; got %@",sum,allLinks] ;
		
		
		
		
		
		/* Filters */
		
		NSSortDescriptor*	sorter		=	[NSSortDescriptor sortDescriptorWithKey:@"cost" ascending:NO] ;
		NSArray*			sorters		=	[NSArray arrayWithObject:sorter] ;
		
		
		
		
		
		/* Helpful functions */
		
		BOOL				(^linkHasActiveEndpoint) (id,NSDictionary*) = ^BOOL(id link,NSDictionary*b){
			NSSet * endpoints = [link endpoints] ;
			for ( id obj in endpoints )
				if ( [networkedNodes containsObject:obj] )
					return YES ;
			return NO ;
		} ;
		BOOL				(^linkHasInactiveEndpoint) (id,NSDictionary*) = ^BOOL(id link,NSDictionary*b){
			NSSet * endpoints = [link endpoints] ;
			for ( id obj in endpoints )
				if ( [unreachedNodes containsObject:obj] )
					return YES ;
			return NO ;
		} ;
		BOOL				(^linkCanBeActivated) (id,NSDictionary*) = ^BOOL(id link,NSDictionary*b){
			return [link distance]<maxRange && linkHasActiveEndpoint(link,b) && linkHasInactiveEndpoint(link,b) ;
		} ;
		
		NSPredicate		*	_linkCanBeActivated			=	[NSPredicate predicateWithBlock:linkCanBeActivated] ;
		
		
		
		
		
		// All links which are candidates for activation
		NSSet			*	(^candidateLinks)(void)		=	^NSSet*{
			return [allLinks filteredSetUsingPredicate:_linkCanBeActivated] ;
		} ;
		OCNodeInfo		*	(^inactiveNodeInLink)(OCLinkInfo*) = ^OCNodeInfo*(OCLinkInfo*link){
			NSSet * endpoints = [link endpoints] ;
			for ( id obj in endpoints )
				if ( [unreachedNodes containsObject:obj] )
					return obj ;
			return 0 ;
		} ;
		
		
		
		
		
		/* Make the Obj-C Nodes */
		
			{
			std::vector<NodeInfo*>::const_iterator	here	=	nodesInfo->nodes().begin() ;
			std::vector<NodeInfo*>::const_iterator	end		=	nodesInfo->nodes().end() ;
			while ( here < end )
				{
				NodeInfo * info = *(here++) ;
				OCNodeInfo * node = [ [OCNodeInfo alloc] initWithNodeInfo:info ] ;
				if ( node.identifier == startNode )
					[networkedNodes addObject:node] ;
				else
					[unreachedNodes addObject:node] ;
				}
			
			// Then verify...
			if ( networkedNodes.count != 1 )
				[NSException raise:NSInternalInconsistencyException format:@"Should only have one start node. Had: %@",networkedNodes] ;
			if ( unreachedNodes.count < 2 )
				[NSException raise:NSInternalInconsistencyException format:@"Algorithm doesn't make sense with <2 other nodes. Had: %@",unreachedNodes] ;
			}
		
		
		
		
		
		/* Loop until we're done */
		
		while ( unreachedNodes.count != 0 )
			{
			NSSet	*	candidates	=	candidateLinks () ;
			
			if ( candidates.count == 0 )
				[NSException raise:NSInternalInconsistencyException format:@"No links are candiates for activation in this iteration. This can happen if there is at least one node outside the range of every other node."] ;
			
			
			NSArray	*	fCandidates	=	[candidates sortedArrayUsingDescriptors:sorters] ;
			
			OCLinkInfo*	cheapestLink=	[fCandidates lastObject] ; // goodbye
			OCNodeInfo*	newNode		=	inactiveNodeInLink ( cheapestLink ) ;
			
			[activeLinks addObject:cheapestLink] ;
			[unreachedNodes removeObject:newNode] ;
			[networkedNodes addObject:newNode] ;
			}
		
		
		
		
		
		/* Assemble the output data */
		
		for ( OCLinkInfo * linkID in activeLinks )
			{
			NSArray	*	nodeInfos	=	[linkID.endpoints allObjects] ;
			if ( nodeInfos.count != 2 )
				[NSException raise:NSInternalInconsistencyException format:@"Expected two endpoints, but got: %@",nodeInfos] ;
			
			OCNodeInfo	*	nodeID1	=	[nodeInfos objectAtIndex:0] ;
			OCNodeInfo	*	nodeID2	=	[nodeInfos objectAtIndex:1] ;
			Node		*	node1	=	nodes -> nodeWithNodeInfo ( nodeID1.info ) ;
			Node		*	node2	=	nodes -> nodeWithNodeInfo ( nodeID2.info ) ;
			Link		*	link	=	Link :: createLink ( linkID.info , node1 , node2 ) ;
			links . push_back ( link ) ;
			}
		}
	
} ;
MinimumSpanningAnalyzer _MinimumSpanningAnalyzer ;













/* Minimum cost routing implementation by Christopher Kemsley */

struct	Route : private std::vector<Identifier>
{
	Route ( Identifier const & inFirstID )
	:	std::vector<Identifier> ()
		{ push_back ( inFirstID ) ; }
	Route ( Route const & copy )
	:	std::vector<Identifier> (copy)
		{ }
	Route ()
	:	std::vector<Identifier> ()
		{ }
	virtual ~Route () { }
	
	
	Route const	operator+	( Identifier const & inID ) const
		{
		Route r ( *this ) ;
		r.push_back(inID) ;
		return r ;
		}
	
	Identifier	firstEntry () const
		{
		return (*this)[0] ;
		}
	
	std::string const	stringRepresentation () const
		{
		Route::const_iterator	here	=	begin() ;
		Route::const_iterator	_end	=	end() ;
		std::stringstream s ;
		s << (*(here++)) ; // safe since we can't construct w/o an ID[0]
		while ( here < _end )
			{
			s << ", " << (*(here++)) ;
			}
		return s.str() ;
		}
} ;

struct	RouteEntry
{
	RouteEntry	( Identifier inSender , Identifier inTarget , Float64 inCost , Route const & inRoute )
	:	sender(inSender) , target(inTarget) , firstHop(inRoute.firstEntry()) , cost(inCost) , route(inRoute.stringRepresentation())
		{ }
	RouteEntry	( RouteEntry const & copy )
	:	sender(copy.sender) , target(copy.target) , firstHop(copy.firstHop) , cost(copy.cost) , route(copy.route)
		{ }
	~RouteEntry () { }
	
	Identifier const	sender ;
	Identifier const	target ;
	Identifier const	firstHop ;
	Float64 const		cost ;
	std::string const	route ;
	
	bool operator==	( RouteEntry const & compare ) const
		{
		if (!( sender == compare.sender ))
			return false ;
		if (!( target == compare.target ))
			return false ;
		if (!( cost == compare.cost ))
			return false ;
		if (!( route == compare.route ))
			return false ;
		return true ;
		}
	// Compares targets
	bool operator<	( RouteEntry const & compare ) const
		{
		return target < compare.target ;
		}
	bool operator>	( RouteEntry const & compare ) const
		{
		return target > compare.target ;
		}
} ;


std::ostream& operator<< ( std::ostream & str , RouteEntry const & entry )
	{
	str << "\n" << entry.sender << "	" << entry.target << "	" << entry.firstHop << "	" << entry.cost << "	" << entry.route ;
	return str ;
	}





struct MinimumSpanningBasedMinimumCostRoutingAnalyzer : Analyzer
{
	MinimumSpanningBasedMinimumCostRoutingAnalyzer () : Analyzer ( "Minimum-Cost (using minimum spanning tree)" ) { }
	
	
	
	static bool containsLink ( LinkVector const & linkSet , Link * inLink )
		{
		LinkVector::const_iterator	here	=	linkSet.begin() ;
		LinkVector::const_iterator	end		=	linkSet.end() ;
		while ( here < end )
			{
			Link * link = *(here++) ;
			if ( link == inLink )
				return true ;
			}
		return false ;
		}
	
	
	static void	buildRoutingTable		(
										 // Generic, persistent information
										 LinkVector const & usedLinks , Identifier origin , Output & output ,
										 // Output table
										 std::set<RouteEntry> & table ,
										 // Information up-to-this-point
										 Node* thisNode , Route const & routeToHere , Float64 costToHere , Link* responsibleLink=0 )
		{
		// Add us to the set (which auto-sorts)
		if ( origin != thisNode->identity->identifier )
			table . insert (  RouteEntry ( origin , thisNode->identity->identifier , costToHere , routeToHere )  ) ;
		
		//output.logOut() << "Got to stone " << (thisNode->identity->identifier) << "\n" ;
		
		// Go through all our links
		LinkVector::const_iterator	here	=	thisNode->links().begin() ;
		LinkVector::const_iterator	end		=	thisNode->links().end() ;
		while ( here < end )
			{
			Link * link = *(here++) ;
			
			//output.logOut() << "	Checking link " << (link->endpoint2->identity->identifier) << "," << (link->endpoint1->identity->identifier) << "\n" ;
			
			// Don't back-track or include other loops
			if ( link == responsibleLink ) continue ;
			if ( ! containsLink(usedLinks,link) ) continue ;
			
			//output.logOut() << "	*** Passed ***\n" ;
			
			// Get the other side of the link
			Node * nextNode ;
			
			if ( link->endpoint1 == thisNode )		nextNode = link->endpoint2 ;
			else if ( link->endpoint2 == thisNode )	nextNode = link->endpoint1 ;
			else	ThrowException ( "MinimumSpanningBasedMinimumCostRoutingAnalyzer" , "Internal inconsistency: link didn't have us as an endpoint" , __FILE__,__LINE__ ) ;
			
			Float64	costToThere		=	costToHere + link->identity->cost() ;
			Route	routeToThere	=	routeToHere + nextNode->identity->identifier ;
			
			buildRoutingTable ( usedLinks,origin,output ,table , nextNode , routeToThere , costToThere , link ) ;
			}
		}
	
	
	
	
	virtual void	analyze		( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , PropertySet const & info , Output & output )
		{
		Float64		maxRange=	20 ; // 20 is the default
		info . getValue ( "maxRange" , maxRange ) ;
		
		UInteger	startNode=	1 ;
		info . getValue ( "referenceNode" , startNode ) ;
		
		
		
		NodeSet	*	nodes		=	NodeSet :: createSetWithNodes(nodesInfo) ;
		LinkVector	links ;
		
		
		
		
		// Get the spanning tree (using existing code)
		MinimumSpanningAnalyzer :: generateTopology ( nodesInfo , linksInfo , maxRange , startNode , nodes , links ) ;
		
		
		
		// Build the table
		std::set<RouteEntry> table ;
		Node	*	rootNode	=	nodes -> nodeWithIdentifier ( startNode ) ;
		
		buildRoutingTable ( links,startNode,output , table , rootNode,Route() , 0 ) ;
		
		
		
		// Calculate the sum
		
		output.tableOut() << "From	To	First Hop	Cost	Full Route" ;
		
		std::set<RouteEntry>::iterator	here	=	table.begin() ;
		std::set<RouteEntry>::iterator	end		=	table.end() ;
		
		while ( here != end )
			{
			RouteEntry const & entry = *(here++) ;
			output.tableOut() << entry ;
			}
		}
	
	
	
	
	
	
	
} ;
MinimumSpanningBasedMinimumCostRoutingAnalyzer _MinimumSpanningBasedMinimumCostRoutingAnalyzer ;











NamespaceEnd
